"""
题目：给定单链表头节点和一个目标值，删除链表中所有值等于目标值的节点，返回删除后的链表头节点。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def remove_all_target(head, target):
    """删除链表中所有值等于target的节点"""
    # 步骤1：处理头节点就是目标值的情况（可能连续多个）
    # 若头节点非空且值为target，直接将头节点后移
    while head and head.val == target:
        head = head.next
    # 至此，如果头节点就是目标值的话 则全部移除了
    # 步骤2：处理非头节点的情况
    current = head  # 当前遍历节点，从新的头节点开始 注意 到这里 curr这个变量肯定不是目标值 不然 上面的while循环会继续把该节点移除掉
    while current and current.next:  # 确保当前节点和下一个节点非空
        # 若下一个节点是目标值，跳过该节点（修改指针）
        if current.next.val == target:
            #这里去掉了目标值后，curr没变，依然继续判断(curr和curr.next)，因为目标值后面那个节点"上来了",要继续判断current.next.val == target
            current.next = current.next.next
        else:
            # 不是目标值，当前节点后移
            current = current.next
    return head
    #上述算法本质就是：在保证curr不是目标值的情况下 判断curr.next是否是目标值 是的话，则移除掉curr.next，让下一个节点顶上来，继续判断该顶上来的节点
    #如果curr.next不是目标值，curr变为curr.next值，按上述逻辑循环判断

"""根据数组创建单链表"""
def create_linked_list(arr):
    #基本判断
    if not arr:
        return None
    #先把第一个摘出来
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

"""遍历链表，返回值列表"""
def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
if __name__ == "__main__":
    # 测试1：中间和末尾有目标值
    head1 = create_linked_list([1, 2, 3, 2, 4])
    new_head1 = remove_all_target(head1, 2)
    print(traverse_linked_list(new_head1))  # 输出: [1, 3, 4]

    # 测试2：头节点是目标值
    head2 = create_linked_list([2, 2, 1, 3])
    new_head2 = remove_all_target(head2, 2)
    print(traverse_linked_list(new_head2))  # 输出: [1, 3]

    # 测试3：所有节点都是目标值
    head3 = create_linked_list([5, 5, 5])
    new_head3 = remove_all_target(head3, 5)
    print(traverse_linked_list(new_head3))  # 输出: []